package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1414 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        final int[] NUMS = {
                1, 2, 3, 5, 8,
                13, 21, 34, 55, 89,
                144, 233, 377, 610, 987,
                1597, 2584, 4181, 6765,
                10946, 17711, 28657, 46368, 75025,
                121393, 196418, 317811, 514229, 832040,
                1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
                102334155, 165580141, 267914296, 433494437, 701408733
        };

        public int findMinFibonacciNumbers(int k) {
            int ans = 0;
            for (int i = NUMS.length - 1; k > 0; --i) {
                int num = NUMS[i];
                ans += k / num;
                k %= num;
            }
            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1414 an = new LC1414();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
